package buildTree;

import java.util.*;

/**
 * @program: data_structures_algorithms
 * @description: 广度，深度优先遍历，使用栈方式
 * @author: lld
 * @create: 2020-11-02 16:37
 **/
public class Test1 {
    public static void main(String[] args) {
        //这里将线性的链表转化成非线性的二叉树，链表节点的顺序恰恰是二叉树前序遍历的顺 序。链表中的空值，代表二叉树节点的左孩子或右孩子为空的情况
        LinkedList<Integer> inputList = new LinkedList<Integer>(Arrays.asList(new Integer[]{3, 2, 9, null, null, 10, null, null, 8, null, 4, null, null}));
        TreeNode treeNode = createBinaryTree(inputList);
//        pre(treeNode);
//        in(treeNode);
//        System.out.println("深度：" + depth(treeNode));
//        levelOrder(treeNode);
//        Test1 test1=new Test1();
//        ArrayList<Integer> arrayList = new ArrayList<>();
//        test1.getKids(treeNode, arrayList);
/*使用引用类型变量
        ArrayList<Integer> list=new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        TreeNode tree=new TreeNode(0),
                tree1=tree;//引用类型变量，内存地址和值均相同
        System.out.println("tree==tree1?"+(tree==tree1));
        for(Integer l:list){
            tree1.right=new TreeNode(l);
            tree1=tree1.right;
        }
        System.out.println(tree.right);

 */
    }

    /**
     * @Description: 构造树结构
     * @Param: [inputList]
     * @return: binaryTree.TreeNode
     **/
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
        TreeNode node = null;
        if (inputList == null || inputList.isEmpty()) {
            return null;

        }
        Integer data = inputList.removeFirst();
        if (data != null) {
            node = new TreeNode(data);
            node.left = createBinaryTree(inputList);
            node.right = createBinaryTree(inputList);
        }
        return node;

    }

    /**
     * @Description: 树的广度优先遍历（层次遍历）
     * @Param: [root]
     * @return: void
     **/
    private static void levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);//首先添加根节点
        while (!queue.isEmpty()) {
            TreeNode treeNode = queue.poll();
            System.out.printf("%d\t", treeNode.data);
            if (treeNode.left != null)
                queue.offer(treeNode.left);
            if (treeNode.right != null)
                queue.offer(treeNode.right);
        }
    }
    /**
     * @Description: 二叉树的深度
     * @Param: [treeNode]
     * @return: int
     **/
    private static int depth(TreeNode treeNode) {
        if (treeNode == null) {
            return 0;
        } else {
            int l = depth(treeNode.left);//左子树深度
            int r = depth(treeNode.right);//右子树深度
            if (l > r) {
                return l + 1;
            } else {

                return r + 1;
            }
        }
    }
  /**
  * @Description: 从左往右输出叶子节点
  * @Param: [root, list]
  * @return: void
  **/
    public void getKids(TreeNode root,ArrayList<Integer> list){
        if(root!=null){
            if(root.left==null&&root.right==null){
                list.add(root.data);
            }
            getKids(root.left, list);
            getKids(root.right, list);
        }

    }
}

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    public TreeNode(int data) {
        this.data = data;
    }

    public TreeNode(int data, TreeNode left, TreeNode right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

//    @Override
//    public String toString() {
//        return "TreeNode{" +
//                "data=" + data +
//                '}';
//    }

    @Override
    public String toString() {
        return "{" +
                "data=" + data +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}

